#include "quickSort1.h"
#include "directSort2.h"
static void Swap(ElementType *a, ElementType *b)
{
    ElementType tmp;
    tmp = *b;
    *b = *a;
    *a = tmp;
}

ElementType Midian3(ElementType A[], int Left, int Right)
{
    int Center = (Left + Right) / 2;
    if (A[Left] > A[Center])
        Swap(&A[Left], &A[Center]);
    if (A[Left] > A[Right])
        Swap(&A[Left], &A[Right]);
    if (A[Center] > A[Right])
        Swap(&A[Center], &A[Right]);
    Swap(&A[Center], &A[Right - 1]);
    return A[Right - 1];
}

#define CutOff (3)

void QSort(ElementType A[], int Left, int Right)
{
    int i, j;
    ElementType Pivot;
    if (Left + CutOff <= Right)
    {
        Pivot = Midian3(A, Left, Right);
        i = Left, j = Right - 1;
        for (;;)
        {
            while (A[++i] < Pivot)
                ;
            while (A[--j] > Pivot)
                ;
            if (i < j)
                Swap(&A[i], &A[j]);
            else
                break;
        }
        Swap(&A[Right - 1], &A[i]);
        QSort(A, Left, i - 1);
        QSort(A, i + 1, Right);
    }
    else
        InsertionSort(A + Left, Right - Left + 1);
}

void QuickSort(ElementType A[], int N)
{
    QSort(A, 0, N - 1);
}
